home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / ada / gwuada_5.zip / adaed / nyudemos / spath.ada < prev    next >
Text File  |  1992-09-01  |  4KB  |  130 lines
  1. -- A parallel  single-source, all-destinations shortest-path finder. 
  2. -- Each  task is  assigned a node,  and tries  to extend the path by 
  3. -- cloning new tasks that explore all successors of that node.
  4. -- The graph is  represented by adjacency lists. This representation
  5. -- is fixed, and global to all tasks.
  6. -- The minimum distances at each step of the computation are kept in
  7. -- arrays RESULT and COMING_FROM. These objects are  monitored by an
  8. -- array of tasks, one for each node, to  yield greater concurrency.
  9.  
  10. with TEXT_IO; use TEXT_IO;
  11. procedure shortest_path is
  12.     package i_io is new integer_io(integer);
  13.     use i_io;
  14.  
  15.     n: integer := 4;                -- cardinality of graph
  16.     subtype graph_size is integer range 1..n;
  17.     subtype graph_node is graph_size ;
  18.     inf: integer := 9999;            -- Infinite distance
  19.  
  20.     type config is array(graph_size) of integer;
  21.     adjacency: array(graph_size) of config;    -- To describe the graph
  22.     result: config := (graph_size => inf);    -- Shortest distances
  23.     coming_from: config;            -- To reconstruct paths
  24. begin
  25.     declare
  26.         task type monitor_node is
  27.         entry init(node: graph_node) ;
  28.  
  29.         entry go_on(pred: graph_node; 
  30.                 pathlength: integer; 
  31.                 shorter: out boolean);
  32.         end monitor_node;
  33.     
  34.     monitor: array(graph_size) of monitor_node ;
  35.  
  36.         task type path is
  37.         entry init(node, pred:  graph_node; 
  38.                pathlength, size: integer);
  39.         end path;
  40.  
  41.         type path_name is access path;
  42.         start: path_name;
  43.         subtype s_path is path;
  44.  
  45.  
  46.         task body monitor_node is
  47.         here: graph_node ;        -- node monitored by this task
  48.         begin
  49.         accept init(node: graph_node) do 
  50.         here := node ; 
  51.         end init ;
  52.  
  53.         loop select
  54.             accept go_on(pred: graph_node;
  55.                  pathlength: integer;
  56.                  shorter:    out boolean) 
  57.             do
  58.                 if pathlength < result(here) then
  59.             -- new path is shorter than previous attempts.
  60.                 result(here) := pathlength;
  61.             coming_from(here) := pred;
  62.                 shorter := true;
  63.                 else
  64.                 shorter := false;
  65.                 end if;
  66.             end go_on;
  67.             or
  68.             terminate;
  69.                 end select;
  70.             end loop;
  71.         end monitor_node;
  72.  
  73.         task body path is
  74.         source, from: graph_node;
  75.         cost,edge: integer;
  76.         options: config;
  77.         x: path_name;
  78.         response: boolean;
  79.         begin
  80.         accept init(node, pred: graph_node;
  81.             pathlength,size: integer) 
  82.         do
  83.             source := node;
  84.         from   := pred;
  85.             cost   := pathlength;
  86.              edge   := size;
  87.         end init;
  88.  
  89.         cost:=cost+edge;
  90.         monitor(source).go_on(from, cost, response);
  91.         if response then    
  92.             -- found shorter path than previous attempts.
  93.         -- Clone successors to explore edges out of this node.
  94.  
  95.             options := adjacency(source) ;
  96.             for j in graph_size loop
  97.             if options(j) /= inf then          -- edge exists;
  98.                 x := new s_path ;          -- new task for it
  99.                 x.init(j, source, cost, options(j));    
  100.             end if;
  101.             end loop;
  102.         end if;
  103.         end path;
  104.  
  105.     begin
  106.         adjacency :=((inf, 9, 2, inf), (inf, 1, 1, 2), 
  107.              (inf, 2, inf, 5), (inf, 1, inf, 2) );
  108.  
  109.     for j in graph_size loop
  110.         -- Attach a monitor_node to each graph node.
  111.         monitor(j).init(j) ;
  112.         end loop ;
  113.  
  114.         start := new path;
  115.     start.init(1, 1, 0, 0);         -- start from node 1, distance 0.
  116.     end;                  -- and wait for tasks to terminate.
  117.  
  118.     put_line("Final distances from source") ;
  119.     new_line; 
  120.  
  121.     for j in graph_size'succ(graph_size'first).. graph_size'last 
  122.     loop 
  123.     put(result(j));
  124.     put("   to  ")  ; put(j) ;
  125.     put("  reached via ")  ; put(coming_from(j)) ; 
  126.     new_line;
  127.     end loop;
  128. end shortest_path;
  129.  
  130.